package com.platform.modules.alg.alglib.poj1986;

public class Poj1986 {
    public String output = "";
    private final int maxn = 80010;
    private int fa[];
    private int head[];
    private int qhead[];
    private int dis[];
    private boolean vis[];
    private int id;
    private int iq;

    Node E[] = new Node[maxn];
    Node QE[] = new Node[maxn];


    int find(int x) {
        if (x != fa[x])
            fa[x] = find(fa[x]);
        return fa[x];
    }

    void LCA(int u) {
        fa[u] = u;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = E[i].next) {
            int v = E[i].to;
            if (!vis[v]) {
                dis[v] = dis[u] + E[i].lca;
                LCA(v);
                fa[v] = u;
            }
        }
        for (int i = qhead[u]; i != -1; i = QE[i].next) {
            int v = QE[i].to;
            if (vis[v]) {
                QE[i].lca = dis[u] + dis[v] - 2 * dis[find(v)];
                QE[i ^ 1].lca = QE[i].lca;
            }
        }
    }

    void add1(int u, int v, int w) {
        E[id].to = v;
        E[id].lca = w;
        E[id].next = head[u];
        head[u] = id++;
    }

    void add2(int u, int v) {
        QE[iq].to = v;
        QE[iq].next = qhead[u];
        qhead[u] = iq++;
    }

    void init() {
        fa = new int[maxn];
        head = new int[maxn];
        for (int i = 0; i < head.length; i++) {
            head[i] = -1;
        }
        qhead = new int[maxn];
        for (int i = 0; i < qhead.length; i++) {
            qhead[i] = -1;
        }
        vis = new boolean[maxn];

        for (int i = 0; i < E.length; i++) {
            E[i] = new Node();
        }
        for (int i = 0; i < QE.length; i++) {
            QE[i] = new Node();
        }

        dis = new int[maxn];

        id = iq = 0;
    }

    public String cal(String input) {
        int N, M, K, u, v, w;
        char s;
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        N = Integer.parseInt(word[0]);
        M = Integer.parseInt(word[1]);
        init();
        for (int i = 0; i < M; i++) {
            String[] info = line[i + 1].split(" ");
            u = Integer.parseInt(info[0]);
            v = Integer.parseInt(info[1]);
            w = Integer.parseInt(info[2]);
            s = info[3].charAt(0);
            add1(u, v, w);
            add1(v, u, w);
        }
        K = Integer.parseInt(line[M + 1]);

        for (int i = 0; i < K; i++) {
            String[] query = line[M + 2 + i].split(" ");
            u = Integer.parseInt(query[0]);
            v = Integer.parseInt(query[1]);
            add2(u, v);//查询也用链式前向星存储
            add2(v, u);
        }
        LCA(1);
        for (int i = 0; i < iq; i += 2)
            output += QE[i].lca + "\n";
        return output;
    }
}

// 图中的边 E 和查询 QE 用统一结构体
class Node {
    public int to;
    public int next;
    public int lca; // lca 表示u、v的边权，查询中 lca 代表查询 u、v 的最短距离
}
